1. Field of the Invention
The present invention relates to Internet Protocol Security (IPSec), and particularly, to a searching method for a Security Policy Database (SPD).
2. Description of the Prior Art
The Virtual Private Network (VPN) applies the technology of the Internet Protocol (IP) to build the encryption tunneling on the Internet so as to establish the enterprise network on the Internet. The network based on the Internet protocol has good expandability, and applies the standard IPSec to be the protection technology. The IP security (IPSec, RFC 2401) combines the security standards of encryption, authentication, key management, digital certification, and so on so as to provide the high protection ability.
When the IPSec is applied for executing the data transmission, the processing can be inbound processing or outbound processing according to the direction of the data transmission. The inbound processing means that via the peer gateway, the data is transmitted from the peer network to the local gateway, and finally, to the local network. The packet received in the inbound processing is called as the inbound packet. There are two kinds of inbound packets. One is the inbound IPSec packet processed by the IPSec, and the other is the general inbound IP packet. The outbound processing means that via the local gateway, the data is transmitted from the local network to the peer gateway, and finally, to the peer network. The packet received by the outbound processing is called as the outbound packet, which is an outbound IP packet.
The IPSec has two different modes, the transport mode and the tunnel mode. The transport mode is a host-to-host encapsulation mechanism, and the tunnel mode is a gateway-to-gateway or gateway-to-host encapsulation. In order words, a host supporting the IPSec has to support the transport mode and the tunnel mode, while the gateway only has to support the tunnel mode. However, the gateway can also support the transport mode so as to provide another selection to make the gateway directly communicate with the host.
The IPSec will determine which packets have to be processed according to the designated selectors, such as the network address, the protocol, and the port number in the SPD. The processing methods comprise applying the IPSec, by-passing the IPSec and discarding. The default processing method is directly discarding the packet. Also, in order to apply the IPSec, the user has to designate the mode of the IPSec, the protocol of the IPSec, the authentication algorithm, the encryption/decryption algorithm, and the key in the Security Association Database (SAD).
The SPD is an ordered list composed of different security policies. Each of the policies is selected according to different selectors. The selectors include the source address, the destination address, the protocol, the source port and the destination port. The range value of each of the selectors can be single, range or wildcard.
Because the selectors may be the same, the overlapping of the policies easily occurs. Namely, in the SPD, the selectors of more than two policies may equally match the searching requirement of one packet. Therefore, IPSec requires the searching of the SPD to be ordered. The searching has to start from the beginning policy and go on sequentially until the first policy matching with the requirement is found so as to obtain a consistent searching result.
FIG. 1 is a perspective diagram of a prior art SPD. If the linear search is directly applied to be the searching method for SPD, the time complexity is O(n), and n is the number of the policies. For the system having a greater number of policies, applying the linear search on the SPD will become the processing bottleneck of the IPSec. Nowadays, the number of the policies in the business product specification is below 100 for the families or small scale enterprises, about 1000 for the middle/large scale enterprises, and about 10000 for the very large scale enterprises.
In the prior art, in order to resolve the problem of searching the SPD, three methods are provided. The first one is the brute force parallel searching method. The second one is the flow-based searching method (disclosed in the U.S. Pat. No. 6,347,376, and the US patent publication number 2003/0023846 and 2003/0069973). Please refer to FIG. 2. The third one is the Patricia-based searching method (disclosed in the U.S. Pat. No. 6,347,376 and the U.S. patent publication No. 2003/0061507). Please refer to FIG. 3.
The brute force parallel searching method directly utilizes the capability of the hardware parallel processing. It divides the number of the policies of the system specification by the maximum number of the policies capable of being processed by a single SPD module so as to determine the number of the SPD modules to be duplicated. The policy manager will collectively manage the searching requirements of the inbound packet or the outbound packet, and then broadcast the requirement to the inbound SPD modules, or the outbound SPD modules for simultaneously searching, and then get the searching result back. If policies matching with the requirement are found out from more than two SPDs, the policy manager will choose the policy with highest priority and report it.
The drawback of this method is the high cost because multiple SPD modules have to be duplicated, and at most, only two searching requirements of the SPDs can be served at the same time. One is the search for the inbound packets, and the other is the search for the outbound packets.
The flow-based searching method will perform some specific processes on each of the packet flow. Take the transport control protocol (TCP) packet for example, the packets having the same source address, destination address, protocol, source port and destination port belong to a packet flow. For the first packet of each of the packet flows, the linear search has to be performed on the SPD so as to obtain the corresponding policy. However, this method will store the search result for being used by the remaining packets in the same packet flow. If the search result is stored in a hash table of which the space usage rate is less than one half, theoretically, the time complexity is O(1).
However, the drawback of this method is that a great amount of memory space is required to maintain the hash table. The space complexity is O(f), and f is the number of packet flows. Furthermore, in this method, the linear search still has to be performed on the SPD for the first packet. Therefore, this may cause a period of delaying before the network program in the application layer builds the network connection.
The Patricia-based searching method applies the Patricia tree to search the data. The Patricia tree is a binary searching tree algorithm. The worst case of the Patricia tree having the non-contiguous masks is O(w2), and w is the length of the key of the Patricia tree. In the method disclosed in the U.S. patent publication number 2003/0061507, w is 112. The drawback of the Patricia-based searching method is that the policies in the SPD cannot be overlapped. Otherwise another effective algorithm is required to transform the original SPD into a non-ordered SPD so that the search result can match the required order by the IPSec. However, in the prior art, the method for transforming the security policy database into the non-ordered security policy database is not provided.
FIG. 4 is a flowchart for processing a prior art outbound IPSec. As for the outbound IP packet (S10), the search is performed on the security policy database (S12). If the search result is “discard,” then the packet is directly discarded (S11). If the search result is “by-pass,” then go to the process for the Internet protocol (S13). If the search result is “apply,” then search the security association database (S15). If not found, then discard the packet, and build the security association (S14). If found, encapsulate the outer header (S16), and then perform the encryption and authentication (S17). Thereafter, go to the process for the Internet protocol (S13).
FIG. 5 is a flowchart for processing a prior art inbound IPSec. As for the inbound IPSec packet (S20), the search is performed on the security association database (S23). If not found (S22), then discard the packet. If found, perform the decryption and the authentication (S24), and then decapsulate the outer header (S25). Thereafter, the search is performed on the security policy database (S26). As for the inbound IP packet (S21), then directly search the security policy database (S26). If a wrong policy is found, then directly discard the packet (S22). If the correct policy is searched, then perform the process for the Internet protocol (S27).